package h0831;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 每日温度
 * @date 2024/8/31 21:38
 */
public class EveryDayTemperature {
    public static void main(String[] args) {
        int[] temps = {73, 74, 75, 71, 69, 72, 76, 73};
        int[] res = dailyTemperatures(temps);
        System.out.println(Arrays.toString(res));
    }

    public static int[] dailyTemperatures(int[] temperatures) {
        //找到右边最高一个
        LinkedList<int[]> stack = new LinkedList<>();
        int n = temperatures.length;
        int[] ans = new int[n];
        stack.addLast(new int[]{temperatures[0], 0});
        for (int i = 1; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > stack.peekLast()[0]) {
                int[] temp = stack.removeLast();
                ans[temp[1]] = i - temp[1];
            }
            stack.addLast(new int[]{temperatures[i], i});
        }
        return ans;
    }
}
